458. Poor Pigs

Posted on | In

458. Poor Pigs

description:

There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?
Answer this question, and write an algorithm for the general case.

General case:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the poisonous bucket within p minutes? There is exactly one bucket with poison.

Note:

A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
After a pig has instantly finished drinking buckets, there has to be a cool down time of m minutes. During this time, only observation is allowed and no feedings at all.
Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).

输入：int buckets, int minutesToDie, int minutesToTest

输出：pig的数量

解答

这道题用了信息论的知识

minutesToTest 是可以测试的时间

minutesToDie 是测试一次需要的时间

所以t = minutesToTest/minutesToDie 就是一共可以测试的次数

我们可以反向理解，给定n个小猪，给定t次测试次数，求最多可以有几个水桶。

当有2个小猪，1个测试次数时
可以有4个水桶，分析如下

水桶 1 2 3 4
喝水情况 00 01 10 11

其中00代表小猪1,2都不喝水桶1的水；01代表小猪1不喝水桶1的水，小猪2在第一轮喝水桶1的水。

当有2个小猪，2个测试次数时（即两轮）,可以有9个水桶：

水桶 1 2 3 4 5 6 7 8 9
喝水情况 00 01 02 10 11 12 20 21 22

其中00代表小猪1,2都不喝水桶1的水；01代表小猪1不喝水桶1的水，小猪2在第一轮喝水桶1的水；21表示小猪1在第二轮喝水桶8的水，小猪2在第一轮喝水桶8的水。

假设5号水桶有毒，则小猪1,2在第一轮全部死亡，只有5号水桶可以做到这一点。
假设6号水桶有毒，则小猪1在第一轮结束后死亡，可以确定水桶4,5,6有问题，又根据小猪2在第一轮结束后存活，可以确定水桶6有问题。
所以根据小猪喝水后死亡的情况，就可以唯一确定一个水桶是有毒的。
所以总结：

可以有的最大水桶数为：（t + 1）n个

反之 需要的小猪数量为log(t + 1)buckets个

代码

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int pig = 0;
        int base = ceil(minutesToTest / minutesToDie) + 1;
        while (pow(base, pig) < buckets) pig ++;
        return pig;
    }
};